package midalgorithms.dynamicplanning;

import java.util.Arrays;

public class _03CoinChange {
    public static int coinChange(int[] coins, int amount) {
        //  动态规划
        //  dp[i] 表示金额为i的时候需要的最小硬币数量！最终目的是求出dp[amount]
        int[] dp = new int[amount + 1];

        //  遍历数组，填充面值存在的dp[i]
        for (int i = 0;i < coins.length;i++){
            if (coins[i] > amount){
                break;
            }
            dp[coins[i]] = 1;
        }
        //  填充dp[]数组
        //  动态规划的核心：找到当前项前面已知项的关系！
        //  dp[i]存在的充分必要条件是：coins中存在一个coin使得dp[i-coin]存在
        for(int i = 1;i<=amount;i++){
            int min = Integer.MAX_VALUE;
            //  此方法类似枚举
            for(int coin: coins){
                if(i>=coin && dp[i-coin] < min){
                    min = dp[i-coin] + 1;
                }
            }
            dp[i] = min;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }

}
